public class L_3_1andL_3_2andL_3_3 {
    /**
     * 二分查找
     */

    static boolean findNum(int[] arr, int num) {
        int L,R,mid,flag;
        L = 0;
        R = arr.length-1;
//        if (R % 2 == 0) {
//            //奇数
//            flag = 1;
//        } else {
//            //偶数
//            flag = 0;
//        }
        while (L <= R) {
            mid = (L + R) / 2;
            if (arr[mid] == num) {
                return true;
            } else if (arr[mid] > num) {
                R = mid - 1;
            } else {
                L = mid + 1;
            }
        }
        return false;
    }

    /**
     * 查找最左边的且 >=num 的数
     * @param arr
     * @param num
     * @return
     */
    static int findLeft(int[] arr, int num) {
        int L,R,mid,ans;
        L = 0;
        R = arr.length-1;
        ans = -1;
        if (arr.length == 0 || arr == null) {
            return ans;
        }
        while (L <= R) {
            mid = (L + R) / 2;
            if (arr[mid] >= num) {
                ans = mid;
                R = mid - 1;
            }else {
                L = mid + 1;
            }
        }
        return ans;
    }

    /**
     * 查找最右边的且 <=num 的数
     * @param arr
     * @param num
     * @return
     */
    static int findRight(int[] arr, int num) {
        int L,R,mid,ans;
        L = 0;
        R = arr.length-1;
        ans = -1;
        if (arr.length == 0 || arr == null) {
            return ans;
        }
        while (L <= R) {
            mid = (L + R) / 2;
            if (arr[mid] <= num) {
                ans = mid;
                L = mid + 1;
            }else {
                R = mid - 1;
            }
        }
        return ans;
    }

    /**
     * 寻找任意一个局部最小值,如果在两边的话,只需要比附近的一个小就是局部最小了
     *
     * @param arr
     * @return
     */
    static int findMin(int[] arr) {
        int L,R,mid,ans;
        L = 0;
        R = arr.length-1;
        ans = -1;

//        if (arr == null || arr.length == 0) {
//            return -1;
//        }
//        int N = arr.length;
//        if (N == 1) {
//            return 0;
//        }
//        if (arr[0] < arr[1]) {
//            return 0;
//        }
//        if (arr[N - 1] < arr[N - 2]) {
//            return N - 1;
//        }
        while (L < R - 1) {
            mid = (L + R) / 2;
            if (arr[mid] < arr[mid - 1] && arr[mid] < arr[mid + 1]) {
                return mid;
            }else{
                if (arr[mid] > arr[mid - 1]) {
                    R = mid - 1;
                }else{
                    L = mid + 1;
                }
            }
        }
        return arr[L] < arr[R] ? L : R;
    }

    /**
     * 验证这个局部最小值是否正确
     * @param arr
     * @param min
     */
    static void checkMin(int[] arr,int min) {
        int N = arr.length;
        if (N == 1 && min == 1) {
            System.out.println("Yes");
        }else if (arr[0] < arr[1]) {
            System.out.println("Yes");
        }else if (arr[N - 1] < arr[N - 2]) {
            System.out.println("Yes");
        }else if (arr[min] < arr[min + 1] && arr[min] < arr[min - 1]) {
            System.out.println("Yes");
        }else {
            System.out.println("No");
        }
    }

    /**
     * 搬运左神的求局部最小值函数
     * @param arr
     * @return
     */
    public static int oneMinIndex(int[] arr) {
        if (arr == null || arr.length == 0) {
            return -1;
        }
        int N = arr.length;
        if (N == 1) {
            return 0;
        }
        if (arr[0] < arr[1]) {
            return 0;
        }
        if (arr[N - 1] < arr[N - 2]) {
            return N - 1;
        }
        int L = 0;
        int R = N - 1;
        // L...R 肯定有局部最小
        while (L < R - 1) {
            int mid = (L + R) / 2;
            if (arr[mid] < arr[mid - 1] && arr[mid] < arr[mid + 1]) {
                return mid;
            } else {
                if (arr[mid] > arr[mid - 1]) {
                    R = mid - 1;
                } else {
                    L = mid + 1;
                }
            }
        }
        return arr[L] < arr[R] ? L : R;
    }

    public static void main(String[] args) {
        int[] arr = {0,1,2,3,4,5,6,7,8,9,10,11,12,15,45,78,88,98,198,256,365,648,1024,2048,3090,4399};
        int[] arr2 = {0,1,1,2,2,3,3,4,4,4,5,5,5,6,6,7,8,9,9,10};
        int[] arr3 = {3,1,2,3,5,6,4,8,9};
        boolean booleanNum = findNum(arr, 9);
        System.out.println(booleanNum);
        System.out.println(findLeft(arr2,4));
        System.out.println(findRight(arr2,4));
        System.out.println(findMin(arr3));
        System.out.println(oneMinIndex(arr3));//发现问题,左神的算法也是不能够跑通arr3这个数组的,奇怪
        checkMin(arr3,6);//但是验证后,6确实是局部最小值
    }
}
